﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Text.RegularExpressions;

namespace NewsMine.Utilities
{
    /// <summary>
    /// source article:
    /// http://fuzzystringmatching.codeplex.com/
    /// </summary>
    public static class FuzzyString
    {
        public static string GetPrimaryKeyString(string input)
        {
            var shingedString = ShingingString(input);
            var sortedHashCode = GetHashCode(shingedString);
            var enCodedKeyString = GetEncodedKeyString(sortedHashCode);
            return enCodedKeyString;
        }

        public static Int32[] GetHashCodeToCompare(string input)
        {
            var shingedString = ShingingString(input);
            var sortedHashCode = GetHashCode(shingedString);
            return sortedHashCode;
        }

        public static double GetSimilarIndex(string inputA, string inputB)
        {
            if (inputA.Trim() == inputB.Trim())
                return 100;
            if (inputA.Trim() == string.Empty)
                return 0;
            if (inputB.Trim() == string.Empty)
                return 0;
            return 100 * GetSimilarIndexByHash(GetHashCodeToCompare(inputA), GetHashCodeToCompare(inputB));
        }


        private static IEnumerable<string> ShingingString(string input)
        {
            string[] splitedStringArray = input.Split(new char[] { ' ', '\n', '.', ',', '\r', '\t' }, StringSplitOptions.RemoveEmptyEntries);
            string[] ret = new string[splitedStringArray.Length - 1];
            for (int i = 0; i < splitedStringArray.Length - 1; i++)
            {
                ret[i] = splitedStringArray[i] + " " + splitedStringArray[i + 1];
            }
            return ret.Distinct();
        }

        private static Int32[] GetHashCode(IEnumerable<string> shingedString)
        {
            List<Int32> hashArray = new List<Int32>();
            foreach (var item in shingedString)
            {
                hashArray.Add(item.GetHashCode());
            }
            return hashArray.OrderBy(i => i).ToArray();

        }

        private static string GetEncodedKeyString(Int32[] hashArray)
        {
            byte[] byteArray = new byte[hashArray.Length * 2];
            for (int i = 0; i < hashArray.Length; i++)
            {
                byteArray[i * 2] = (byte)(hashArray[i] & 0xFF);
                byteArray[i * 2 + 1] = (byte)((hashArray[i] & 0xff00) >> 8);
            }
            string returnValue = System.Convert.ToBase64String(byteArray);
            return returnValue;
        }

        private static Int32[] ParsePrimiaryKeyString(string pkString)
        {
            byte[] encodedDataAsBytes = System.Convert.FromBase64String(pkString);
            Debug.Assert(encodedDataAsBytes.Length % 2 == 0, "The byte length has to be odd number");
            Int32[] convertTo32Bit = new Int32[encodedDataAsBytes.Length / 2];
            for (int i = 0; i < encodedDataAsBytes.Length; i += 2)
            {
                convertTo32Bit[i / 2] = (Int32)encodedDataAsBytes[i] + (Int32)encodedDataAsBytes[i + 1] << 8;
            }
            return convertTo32Bit;
        }

        private static double GetSimilarIndexByHash(Int32[] setA, Int32[] setB)
        {
            double similarIndex = (double)(setA.Intersect(setB).Count()) / (double)(setA.Union(setB).Count());
            return similarIndex;
        }
    }


    /// <summary>
    /// Source article
    /// http://www.codeproject.com/Articles/36869/Fuzzy-Search
    /// </summary>
    public class FuzzySearch
    {
        /// <summary>
        /// Calculates the Levenshtein-distance of two strings.
        /// </summary>
        /// <param name="src">
        /// 1. string
        /// </param>
        /// <param name="dest">
        /// 2. string
        /// </param>
        /// <returns>
        /// Levenshstein-distance
        /// </returns>
        /// <remarks>
        /// See 
        /// <a href='http://en.wikipedia.org/wiki/Levenshtein_distance'>
        /// http://en.wikipedia.org/wiki/Levenshtein_distance
        /// </a>
        /// </remarks>
        public static int LevenshteinDistance(string src, string dest)
        {
            int[,] d = new int[src.Length + 1, dest.Length + 1];
            int i, j, cost;
            char[] str1 = src.ToCharArray();
            char[] str2 = dest.ToCharArray();

            for (i = 0; i <= str1.Length; i++)
            {
                d[i, 0] = i;
            }
            for (j = 0; j <= str2.Length; j++)
            {
                d[0, j] = j;
            }
            for (i = 1; i <= str1.Length; i++)
            {
                for (j = 1; j <= str2.Length; j++)
                {

                    if (str1[i - 1] == str2[j - 1])
                        cost = 0;
                    else
                        cost = 1;

                    d[i, j] =
                        Math.Min(
                            d[i - 1, j] + 1,					// Deletion
                            Math.Min(
                                d[i, j - 1] + 1,				// Insertion
                                d[i - 1, j - 1] + cost));		// Substitution

                    if ((i > 1) && (j > 1) && (str1[i - 1] == str2[j - 2]) && (str1[i - 2] == str2[j - 1]))
                    {
                        d[i, j] = Math.Min(d[i, j], d[i - 2, j - 2] + cost);
                    }
                }
            }

            return d[str1.Length, str2.Length];
        }


        /// <summary>
        /// Calculates the Levenshtein-distance of two strings.
        /// </summary>
        /// <param name="src">
        /// 1. string
        /// </param>
        /// <param name="dest">
        /// 2. string
        /// </param>
        /// <returns>
        /// Levenshstein-distance
        /// </returns>
        /// <remarks>
        /// See 
        /// <a href='http://en.wikipedia.org/wiki/Levenshtein_distance'>
        /// http://en.wikipedia.org/wiki/Levenshtein_distance
        /// </a>
        /// </remarks>
        public static int LevenshteinDistanceWordLevel(string src, string dest)
        {
           
            int i, j, cost;
            string[] str1 = src.Split(new char[] {',',' ','.' }, StringSplitOptions.RemoveEmptyEntries);
            string[] str2 = dest.Split(new char[] { ',', ' ', '.' }, StringSplitOptions.RemoveEmptyEntries);

            int[,] d = new int[str1.Length + 1, str2.Length + 1];

            for (i = 0; i <= str1.Length; i++)
            {
                d[i, 0] = i;
            }
            for (j = 0; j <= str2.Length; j++)
            {
                d[0, j] = j;
            }
            for (i = 1; i <= str1.Length; i++)
            {
                for (j = 1; j <= str2.Length; j++)
                {

                    if (str1[i - 1] == str2[j - 1])
                        cost = 0;
                    else
                        cost = 1;

                    d[i, j] =
                        Math.Min(
                            d[i - 1, j] + 1,					// Deletion
                            Math.Min(
                                d[i, j - 1] + 1,				// Insertion
                                d[i - 1, j - 1] + cost));		// Substitution

                    if ((i > 1) && (j > 1) && (str1[i - 1] == str2[j - 2]) && (str1[i - 2] == str2[j - 1]))
                    {
                        d[i, j] = Math.Min(d[i, j], d[i - 2, j - 2] + cost);
                    }
                }
            }

            return d[str1.Length, str2.Length];
        }

        public static double SimilarityOfTwoStrings(string src, string dest)
        {
            List<string> matchedKeywords = new List<string>();

            return SimilarityOfTwoStrings(src, dest, out matchedKeywords);
        }
        public static double SimilarityOfTwoStrings(string src, string dest,out List<string> matchedKeywords)
        {
            src = src.ToLower();
            dest = dest.ToLower();
            src = TempAnalyzer.RemoveAllSpecialCharacterForIndexing(src);
            dest = TempAnalyzer.RemoveAllSpecialCharacterForIndexing(dest);
            var srcArray = src.Split(' ');
            var destArray = dest.Split(' ');
            matchedKeywords = srcArray.Intersect(destArray).ToList();
            return matchedKeywords.Count;
            //return (srcArray.Intersect(destArray).Count() * 100) / Math.Max(srcArray.Length, destArray.Length);
        }

        //---------------------------------------------------------------------
        /// <summary>
        /// Fuzzy searches a list of strings.
        /// </summary>
        /// <param name="word">
        /// The word to find.
        /// </param>
        /// <param name="wordList">
        /// A list of word to be searched.
        /// </param>
        /// <param name="fuzzyness">
        /// Ration of the fuzzyness. A value of 0.8 means that the 
        /// difference between the word to find and the found words
        /// is less than 20%.
        /// </param>
        /// <returns>
        /// The list with the found words.
        /// </returns>
        /// <example>
        /// 
        /// </example>
        public static List<string> Search(
            string word,
            List<string> wordList,
            double fuzzyness)
        {
#if !LINQ
            List<string> foundWords = new List<string>();

            foreach (string s in wordList)
            {
                // Calculate the Levenshtein-distance:
                int levenshteinDistance =
                    LevenshteinDistance(word, s);

                // Length of the longer string:
                int length = Math.Max(word.Length, s.Length);

                // Calculate the score:
                double score = 1.0 - (double)levenshteinDistance / length;

                // Match?
                if (score > fuzzyness)
                    foundWords.Add(s);
            }
#else
			// Tests have prove that the !LINQ-variant is about 3 times
			// faster!
			List<string> foundWords =
				(
					from s in wordList
					let levenshteinDistance = LevenshteinDistance(word, s)
					let length = Math.Max(s.Length, word.Length)
					let score = 1.0 - (double)levenshteinDistance / length
					where score > fuzzyness
					select s
				).ToList();
#endif
            return foundWords;
        }


        public static List<string> SearchByWordLevel(
           string word,
           List<string> wordList,
           double fuzzyness)
        {
#if !LINQ
            List<string> foundWords = new List<string>();

            foreach (string s in wordList)
            {
                // Calculate the Levenshtein-distance:
                int levenshteinDistance =
                    LevenshteinDistanceWordLevel(word, s);

                // Length of the longer string:
                int length = Math.Max(word.Length, s.Length);

                // Calculate the score:
                double score = 1.0 - (double)levenshteinDistance / length;

                // Match?
                if (score > fuzzyness)
                    foundWords.Add(s);
            }
#else
			// Tests have prove that the !LINQ-variant is about 3 times
			// faster!
			List<string> foundWords =
				(
					from s in wordList
					let levenshteinDistance = LevenshteinDistance(word, s)
					let length = Math.Max(s.Length, word.Length)
					let score = 1.0 - (double)levenshteinDistance / length
					where score > fuzzyness
					select s
				).ToList();
#endif
            return foundWords;
        }

    }



    /// <summary>
    /// This class implements string comparison algorithm
    /// based on character pair similarity
    /// Source: http://www.catalysoft.com/articles/StrikeAMatch.html
    /// </summary>
    public class SimilarityTool
    {
        /// <summary>
        /// Compares the two strings based on letter pair matches
        /// </summary>
        /// <param name="str1"></param>
        /// <param name="str2"></param>
        /// <returns>The percentage match from 0.0 to 1.0 where 1.0 is 100%</returns>
        public double CompareStrings(string str1, string str2)
        {
            List<string> pairs1 = WordLetterPairs(str1.ToUpper());
            List<string> pairs2 = WordLetterPairs(str2.ToUpper());

            int intersection = 0;
            int union = pairs1.Count + pairs2.Count;

            int count = pairs1.Intersect(pairs2).Count();

            for (int i = 0; i < pairs1.Count; i++)
            {
                for (int j = 0; j < pairs2.Count; j++)
                {
                    if (pairs1[i] == pairs2[j])
                    {
                        intersection++;
                        pairs2.RemoveAt(j);//Must remove the match to prevent "GGGG" from appearing to match "GG" with 100% success

                        break;
                    }
                }
            }

            //return (1.0 * intersection) / Math.Max(pairs1.Count, pairs2.Count);
            return (2.0 * intersection) / union;
        }

        /// <summary>
        /// Gets all letter pairs for each
        /// individual word in the string
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        private List<string> WordLetterPairs(string str)
        {
            List<string> AllPairs = new List<string>();

            // Tokenize the string and put the tokens/words into an array
            string[] Words = Regex.Split(str, @"\s");

            // For each word
            for (int w = 0; w < Words.Length; w++)
            {
                if (!string.IsNullOrEmpty(Words[w]))
                {
                    // Find the pairs of characters
                    String[] PairsInWord = LetterPairs(Words[w]);

                    for (int p = 0; p < PairsInWord.Length; p++)
                    {
                        AllPairs.Add(PairsInWord[p]);
                    }
                }
            }

            return AllPairs;
        }

        /// <summary>
        /// Generates an array containing every 
        /// two consecutive letters in the input string
        /// </summary>
        /// <param name="str"></param>
        /// <returns></returns>
        private string[] LetterPairs(string str)
        {
            int numPairs = str.Length - 1;

            string[] pairs = new string[numPairs];

            for (int i = 0; i < numPairs; i++)
            {
                pairs[i] = str.Substring(i, 2);
            }

            return pairs;
        }
    }
}
